package memnet.graph.search;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

import memnet.graph.Edge;
import memnet.graph.EdgeData;
import memnet.graph.Graph;
import memnet.graph.Node;


public class UniformCost {
	
	public static void main(String[] args) {
		Graph gph = new Graph();
		gph.setEdge("s", "a", "eat", 1);
		gph.setEdge("s", "a", "like", 2);
		gph.setEdge("s", "g", "like", 5);
		gph.setEdge("a", "s", "like", 5);
		gph.setEdge("g", "s", "blah", 0);
		gph.setEdge("a", "g", "poop", 1);
		/*
		Node s = gph.getNode("s");
		Node a = gph.getNode("a");
		Node g = gph.getNode("g");
		s.setEdge(a, new EdgeData("eat"), 1);
		s.setEdge(a, new EdgeData("like"), 2);
		s.setEdge(g, new EdgeData("like"), 5);
		a.setEdge(s, new EdgeData("like"), 5);
		g.setEdge(s, new EdgeData("blah"),0);
		a.setEdge(g, new EdgeData("poop"), 1);
		*/
		
		System.out.println(gph.getOutgoingEdges("s"));
		System.out.println("---");
		SearchResult results = search(gph, "s","g");
		System.out.println(results);
		/*
		for( SearchResult ucr : results){
			System.out.println(ucr.path);
			System.out.println(ucr.backCost);
		}*/
	}
	

	/**
	 * Returns null if failure
	 * @param graph
	 * @param start
	 * @param goal
	 * @return
	 */
	public static SearchResult search(Graph graph, Object start, Object goal){
		PriorityQueue<SearchResult> fringe = new PriorityQueue<SearchResult>();
		Set<Edge> closedSet = new HashSet<Edge>();
		
		ArrayList<Edge> path = new ArrayList<Edge>();
		//add a dummy edge so the fringe does not start empty
		path.add( new Edge(graph.getNode(start),graph.getNode(start),0,(EdgeData)null));
		fringe.add( new SearchResult(start, path, 0,0));
		
		while(! fringe.isEmpty()){
			SearchResult current = fringe.remove();
			
			Object currentNode = current.lastEdge().dst.data();
			
			//System.out.println("Expanding: "+currentNode);
			
			if( currentNode.equals(goal)){
				//System.out.println("Goal!");
				current.removeHead();
				return current;
			}
			
			if( !closedSet.contains(current.lastEdge())){
				closedSet.add(current.lastEdge());
				//System.out.println(graph.getOutgoingEdges(currentNode));
				
				for( Edge successor : graph.getOutgoingEdges(currentNode)){
					List<Edge> newPath = new ArrayList<Edge>(current.path);
					newPath.add(successor);
					double cost = current.backCost + successor.getWeight();
					fringe.add( new SearchResult(successor, newPath, cost,0));
					
				}
			}
			
		}
		
		return null;
	}
	
	/**
	 * Returns the n lowest cost paths that do not share any intermediate nodes
	 * @param n
	 * @param graph
	 * @param start
	 * @param goal
	 * @return
	 */
	/*
	public static ArrayList<SearchResult> exhaustiveSearch(int n, NodeGraph graph, Object start, Object goal){
		ArrayList<SearchResult> results = new ArrayList<SearchResult>();
		PriorityQueue<SearchResult> fringe = new PriorityQueue<SearchResult>();
		Set<Object> closedSet = new HashSet<Object>();
		
		ArrayList<Object> path = new ArrayList<Object>();
		path.add(start);
		fringe.add( new SearchResult(start, path, 0,0));
		while(! fringe.isEmpty()){
			SearchResult current = fringe.remove();
			
			if( current.currentNode().equals(goal)){
				results.add(current);
				if( results.size()>=n)
					break;
				continue;
			}
			
			if( !closedSet.contains(current.currentNode())){
				closedSet.add(current.currentNode());
				
				for( Object successor : graph.getNeighbors(current.currentNode())){
					List<Object> newPath = new ArrayList<Object>(current.path);
					newPath.add(successor);
					double cost = current.backCost + graph.getEdgeWeight(current.currentNode(), successor);
					fringe.add( new SearchResult(successor, newPath, cost,0));
				}
			}
			
		}
		
		return results;
	}
	*/
}

